package com.xy.algorithm;

/**
 * 汉诺塔问题：
 * 相传在古印度圣庙中，有一种被称为汉诺塔(Hanoi)的游戏。
 * 该游戏是在一块铜板装置上，有三根杆(编号A、B、C)，在A杆自下而上、由大到小按顺序放置64个金盘(如下图)。
 * 游戏的目标：把A杆上的金盘全部移到C杆上，并仍保持原有顺序叠好。
 * 操作规则：每次只能移动一个盘子，并且在移动过程中三根杆上都始终保持大盘在下，小盘在上，操作过程中盘子可以置于A、B、C任一杆上
 * @author x
 */
public class Hanoi {

    public static void hanoi(int n, String a, String b, String c) {
        if (n > 0) {
            /**
             * 假设a，b，c为三根柱子
             * 1.把上面n-1个盘子从a柱经过c柱移动到b柱
             * 2.把最后一个盘子从a柱移动到c柱
             * 3.把b柱上的n-1个盘子经过a柱移动到c柱
             */
            hanoi(n -1 , a, c, b);
            System.out.println("moving from " + a + " to " + c);
            hanoi(n - 1, b, a, c);
        }
    }

    public static void main(String[] args) {
        long startTime = System.currentTimeMillis();
        hanoi(30, "A", "B", "C");
        long endTime = System.currentTimeMillis();
        System.out.println(endTime - startTime);
    }
}
